#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int64_t table[45][4];
int64_t result[45] = {0};

void prepare() {
    for (int n = 0; n < 45; n++) {
        for (int i = 0; i < 4; i++) {
            if (n == 0) {
                table[n][i] = 1;
            } else {
                int min = MAX(i - 2, 0);
                int max = MIN(i + 2, 3);
                int64_t res = 0;
                for (int j = min; j <= max; j++) {
                    if (i != j) {
                        res += table[n - 1][j];
                    }
                }
                table[n][i] = res;
            }
        }
        for (int i = 0; i < 4; i++) {
            result[n] += table[n][i];
        }
    }
}

int main(void) {
    prepare();
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int n;
        scanf("%d", &n);
        printf("%" PRId64 "\n", result[n - 1]);
    }
}
